package com.tys.algorithm.bak.code1;

import java.util.Comparator;
import java.util.PriorityQueue;

//数组实现大根堆
public class Code29_Heap {
    //大根堆：二叉树
    public static class MyMaxHeap {
        private int[] heap; //存储堆数据
        private final int limit; //堆数组最大限制
        private int heapSize; //当前堆大小

        public MyMaxHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }

        //判断堆是否为null
        public boolean isEmpty() {
            return heapSize == 0;
        }

        //堆是否满了
        public boolean isFull() {
            return heapSize == limit;
        }

        //值加入堆
        public void push(int value) {
            if (heapSize == limit) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }

        //从下向上移动
        //新加来的数，停在index位置，依次向上移动
        //移动到0位置，或替代不了父节点，则停止
        //index的父节点 = (index - 1) / 2
        private void heapInsert(int[] arr, int index) {
            //index节点>父节点
            while (arr[index] > arr[(index - 1) / 2]) {
                //交换index节点和父节点
                swap(arr, index, (index - 1) / 2);
                //index移动到父节点
                index = (index - 1) / 2;
            }
        }

        //返回最大值，在大根堆中把最大值删掉
        //剩下的依然保持大根堆组织
        public int pop() {
            int ans = heap[0]; //弹出头
            swap(heap, 0, --heapSize); //将头放到最后，需要先将长度--
            heapify(heap, 0, heapSize);
            return ans;
        }

        //从上向下移动
        //从index位置，向下看，不断下沉
        //停：较大的孩子都不比index大，或者没孩子
        private void heapify(int[] arr, int index, int heapSize) {
            int left = index * 2 + 1; //左孩子下标
            while (left < heapSize) {//判断有没有左孩子
                //较大孩子的下标largest
                //右孩子下标=left+1
                //有右孩子并且右孩子大则右孩子给largest
                //其他情况左孩子给largest
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                //较大孩子和index对比哪个大
                largest = arr[largest] > arr[index] ? largest : index;
                if (largest == index) { //孩子没有比index大则退出
                    break;
                }
                //index和较大孩子交换
                swap(arr, largest, index);
                index = largest; //移动index
                left = index * 2 + 1;//左孩子
            }
        }

        //交换
        private void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    //乱序堆，出堆暴力循环找堆的最大值
    public static class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;//下一个放的位置

        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }

        //判断数组是否为空
        public boolean isEmpty() {
            return size == 0;
        }

        //判断数组是否满了
        public boolean isFull() {
            return size == limit;
        }

        //加入数组
        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            //入堆直接加，没有顺序
            arr[size++] = value;
        }

        //取出数组中最大值
        public int pop() {
            int maxIndex = 0; //堆中最大值索引
            //遍历整个堆
            for (int i = 1; i < size; i++) {
                //找最大值
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            //删除最大值
            //将最后一个数填充到删除的位置，总长度-1，乱序不在乎顺序
            arr[maxIndex] = arr[--size];
            return ans;
        }
    }

    //比较器：从大到小排
    public static class MyComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

    public static void main(String[] args) {
        //默认小根堆
        PriorityQueue<Integer> heap1 = new PriorityQueue<>();
        heap1.add(5);
        heap1.add(3);
        System.out.println("peek heap1 min:" + heap1.peek());

        //指定比较器：从大到小
        PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
        heap.add(5);
        heap.add(3);
        System.out.println("peek heap max:" + heap.peek());
        heap.add(7);
        heap.add(0);
        System.out.println("peek heap max:" + heap.peek());
        //可以加重复值
        heap.add(7);
        heap.add(0);
        heap.add(7);
        heap.add(0);
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
        int value = 1000;//值
        int limit = 100;//最大长度
        int testTimes = 100000;//测试次数
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1; //随机数组最大长度1 ~ limit+1
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);//随机循环次数0-limit
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                }
                if (my.isEmpty()) { //为空加数据
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) { //满了
                    if (my.pop() != test.pop()) { //取数不一致
                        System.out.println("Oops!");
                    }
                } else {
                    //随机加数和取数
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
        }
        System.out.println("finish");
    }
}
